class Solution {
    int memo[][];


    public int countDigitOne(int n) {
        char[] s = Integer.toString(n).toCharArray();
        int m = s.length;
        memo = new int[m][m];
        for(int i = 0;i<m;i++)
        {
            Arrays.fill(memo[i],-1);
        }
        return f(0,0,true,memo,s);

    }

    public int f(int i,int cns1,boolean is_limit,int[][] memo,char[] s)
    {
        if(i==s.length)
        {
            return cns1;
        }
        if(!is_limit&&memo[i][cns1]>=0)
        {
            return memo[i][cns1];
        }
        int res = 0;
        int up = is_limit?s[i]-'0':9;
        for(int d =0;d<=up;d++)
        {
           
               res+=f(i+1,cns1+(d==1?1:0),is_limit&&d==up,memo,s);
            
        }
        if(!is_limit)
        {
           memo[i][cns1]=res;
        }
        return res;
    }
}